package qsc.algorithm.primAlgorithm;

import java.util.ArrayList;

/**
 * @auther QiuShangcheng
 * @create 2021/5/3
 */
public class Review {

    public static void main(String[] args) {
        //邻接矩阵
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verxs = data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000}
        };
        MGraph graph = new MGraph(7, data, weight);
        graph.showMGraph();
        review(graph, 0);
    }

    public static void review(MGraph graph, int begin) {
        //记录当前节点已被访问
        graph.getVisited()[begin] = true;
        //存储每次选取的节点
        ArrayList<Integer> res = new ArrayList<>();
        res.add(begin);
        //存储最小的边
        int minNum;
        for (int i = 0; i < graph.getVerxs() - 1; i++) {
            minNum = 10000;
            int point1 = begin;
            int point2 = begin;
            for (int j = 0; j < res.size(); j++) {
                int[] curLink = graph.getWeight()[res.get(j)];
                for (int k = 0; k < curLink.length; k++) {
                    if (curLink[k] < minNum && graph.getVisited()[k] == false) {
                        minNum = curLink[k];
                        point1 = k;
                        point2 = res.get(j);
                    }

                }
            }
            res.add(point1);
            graph.getVisited()[point1] = true;
            System.out.println("边<" + graph.getData()[point1] + "," + graph.getData()[point2] + "> 权值:" + graph.getWeight()[point2][point1]);
        }

    }
}
